package fun.coding.leetcode;

public class MinimumPathSum {

	public static void main(String[] args) {

	}

	// TODO: 2 dimensional array DP could be further optimized to only use 1 dimension
	public int minPathSum(int[][] grid) {
		// validate the two dimensional array
		if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
		
		int row = grid.length;
		int col = grid[0].length;
		
		int[][] lookup = new int[row + 1][col + 1];
		for (int i = 0; i <= row; i++) {
			lookup[i][0] = Integer.MAX_VALUE;
		}
		for (int j = 0; j <= col; j++) {
			lookup[0][j] = Integer.MAX_VALUE;
		}
		
		lookup[0][1] = 0;
		lookup[1][0] = 0;
		
		for (int i = 1; i <= row; i++) {
			for (int j = 1; j <= col; j++) {
				lookup[i][j] = Math.min(lookup[i-1][j], lookup[i][j-1]) + grid[i-1][j-1];
			}
		}
		
		return lookup[row][col];
	}
}
